With the development of computers and electronic devices, data input and control have become one of the fundamental problems of computer-human interaction. Typical data input systems are usually based on language writing systems with elementary input actions corresponding to symbols of language script system. The most common implementation of such script-based input system is the keyboard with input keys representing symbols of scripts. Legacy computer keyboard were designed for two-hands input, and are modifications of typewriter keyboards.
Miniaturization of electronic devices in general and development of mobile devices, especially, caused a lot of issues with input and control of such devices. Limited screen and surface area of mobile and wearable devices doesn't provide enough space for a convenient hardware or virtual keyboard, but miniature keyboards may be difficult to use.
Many mobile devices are designed for one hand operation in portrait mode and are tall and narrow, further limiting the space for a keyboard in the portrait mode and reducing the size of keys. Operating the device with such miniature keys leads to many input errors and ambiguity of input. Persons with vision and motion disabilities often can't use such devices due these issues. Another problem of virtual keyboards is that they have very different key sizes and distances between keys for portrait and landscape modes.
Different approaches have been proposed for the aforementioned problems. Most approaches don't modify the arrangement of keys, but use different methods of prediction, disambiguation and correction of input to reduce the number of input errors and ambiguity. That doesn't eliminate the source of the problems, but just treats its consequences.
Another approach is based on assignment of several input meanings to several larger keys and disambiguating of input by directional flicks, multi-tap or word disambiguation. These approaches are very often used for hardware phone keypads. The Fastap keyboard (U.S. Pat. No. 7,126,498 to Levy) uses a square matrix of small contact keys. Different combinations of simultaneously pressed keys represent different input meanings. Such non-traditional layouts and input methods are difficult to learn and use. User research shows that 83% of users prefer entering text on a familiar QWERTY layout.
The Delta II keyboard described in U.S. Pat. No. 7,658,562 to Suess provides another approach to the problem. It uses a rectangular matrix arrangement with 6 rows of 5 keys to represent all 26 alphabetic keys of QWERTY keyboard. This arrangement provides an increase of key size, comparing to the legacy QWERTY keyboard of the same width, but unfortunately as it described later, such square key arrangements have the smallest key sizes among other possible key arrangements. Also due the fixed nature of the arrangement, the width of a keyboard strictly determines the size of keys and it cannot be changed and adjusted to user needs and different screen sizes without deformation of key shapes.
A keyboard with keys of variable shapes and areas to represent more frequent letters with bigger keys is described in U.S. Pat. No. 7,372,454 to Betts-LaCroix. The approach is based on the area of keys, but as it was found that the distance between key centers, but not their area, is the determining factor for efficient input. Another issue for this keyboard is that shapes of keys are different and non-convex.
As disclosed in “Observational and Experimental Investigation of Typing Behaviour using Virtual Keyboards on Mobile Devices” by Niels Henze, Enrico Rukzio, and Susanne Boll, keyboards users tend to select some “target” point of a key shape in the process of key pointing. These target points are close to geometric center of a key's shape. Positions of key touches are normally distributed around these target points. In typical implementations of virtual keyboards, the key with the target point closest to a touch position is selected as the input key.
Target points of keys determine a subdivision of a plane into cells of a Voronoi diagram. Each cell comprises a polygon with inner points are closest to target point within a cell. Therefore, touch positions within a cell of Voronoi diagram are recognized as inputs for a key corresponding to this cell. To improve touch recognition and to increase areas of cells, the minimal distance from target points to the border of their Voronoi cell should be maximized. This is equivalent to maximization of distances between target points of keys itself. That leads to the spreading point optimization problem: to find positions of given number of points within a container of a given shape, which maximizes a minimal distance between points. Keys with centers in these positions will provide the optimal key arrangements with the maximum spreading of keys.
There is a known geometry problem of point spreading within a square. As disclosed in “Packing Circles in a Square: A Review and New Results”, Peikert et al., this problem is equivalent to the dual problem of optimal packing of unit circles within a square shape, i.e. to find a smallest square, containing given number of unit circles. Both, these problems are not yet solved in the general case, but there are approaches for many particular cases for given numbers of circles. Similar problems of optimal unit circle packing within different shapes are described and demonstrated by packomania. The best-known approaches for different numbers of unit circles within rectangles of variable shapes are also provided there.
A variety of iterative numeric optimization methods are developed to solve point spreading and circle packing problems in the general case. Many of these arrangements of keys are unstructured, non-periodic and keys may be adjacent to different number of other keys. They may be loose and have keys, which are not adjacent to any other keys. Therefore, these arrangements are no well suited for use as keyboard arrangements.
Many user interfaces are based on selection of an object from a grid of objects, for example, application icons at home screens of different operational systems, options in application menus. Usually, such interfaces are fixed and are not adjustable to windows of different sizes. Resizing of windows may lead to a rearrangement and hiding of some elements of grid interfaces.